﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Heap
{

    public class FlexHeap<T>
    {

        private BinaryTree<T> m_Heap;
        private int m_Type;											// 0 min heap, 1 max heap
        private int COMPARE_TYPE;

        /**
         * Construct a FlexHeap by specifying the type : 0 for a min heap and 1 for a max heap
         * @param _i
         */
        public FlexHeap(int _i, int _COMPARE_TYPE)
        {
            this.m_Heap = new BinaryTree<T>();
            this.m_Type = _i;
            this.COMPARE_TYPE = _COMPARE_TYPE;
        }


        /**
         * Add an element with a given key and value
         * @param _key
         * @param _value
         */
        public void AddElement(ConstraintKey _key, T _value)
        {
            this.m_Heap.AddNode(_key, _value);
            this.HeapUp(this.m_Heap.getM_size() - 1);
        }

        /**
         * Add an element from an existing node
         * @param _node
         */
        public void AddElement(Node _node)
        {
            this.m_Heap.AddNode(_node.getM_Key(), (T)_node.getM_Value());
            this.HeapUp(this.m_Heap.getM_size() - 1);
        }

        /**
         * Remove and return the root of the heap
         * @return	The node being removed
         */
        public Node Remove()
        {
            Node tmpNode = new Node(getRoot().getM_Key(), getRoot().getM_Value(), 0);

            Node lastNode = this.m_Heap.Get(this.m_Heap.getM_size() - 1);
            this.m_Heap.Set(0, lastNode);
            this.m_Heap.Set(this.m_Heap.getM_size() - 1, null);


            HeapDown(0);
            this.m_Heap.setM_size(this.m_Heap.getM_size() - 1);
            return tmpNode;
        }

        /**
         * Swap a node with its parent if required by the heap type
         * @param _nodeIndex
         */
        private void HeapUp(int _nodeIndex)
        {
            Node parent, node;
            bool todo = false;

            if (_nodeIndex != 0)
            {
                parent = this.m_Heap.getParent(_nodeIndex);
                node = this.m_Heap.Get(_nodeIndex);

                if ((this.m_Type == 0) && (parent.getM_Key().CompareTo(node.getM_Key()) >= 0))
                    todo = true;
                else if ((this.m_Type == 1) && (parent.getM_Key().CompareTo(node.getM_Key()) == -1))
                    todo = true;

                if (todo)
                {
                    SwapNodes(parent, node);
                    HeapUp(parent.getM_Index());
                }
            }


        }

        /**
         * Swap a node with its children if required by the heap type
         * @param _nodeIndex
         */

        private void HeapDown(int _nodeIndex)
        {
            if (_nodeIndex != this.m_Heap.getM_size() - 1)
            {
                Node root, leftChild, rightChild;
                Node node = null;
                bool todo = true;

                root = this.m_Heap.Get(_nodeIndex);
                leftChild = this.m_Heap.getLeftChild(_nodeIndex);
                rightChild = this.m_Heap.getRightChild(_nodeIndex);

                if (this.m_Heap.hasChildren(root.getM_Index()))
                {
                    if ((rightChild != null) && (leftChild == null))
                        node = rightChild;
                    else if ((rightChild == null) && (leftChild != null))
                        node = leftChild;
                    else
                    {
                        if ((this.m_Type == 0))
                        {
                            node = (leftChild.getM_Key().CompareTo(rightChild.getM_Key()) >= 0) ? rightChild : leftChild;
                            if (root.getM_Key().CompareTo(node.getM_Key()) == -1)
                                todo = true;
                        }
                        else if ((this.m_Type == 1))
                        {
                            node = (leftChild.getM_Key().CompareTo(rightChild.getM_Key()) == -1) ? rightChild : leftChild;
                            if (root.getM_Key().CompareTo(node.getM_Key()) == -1)
                                todo = true;
                        }

                        if (todo)
                        {
                            SwapNodes(root, node);
                            HeapDown(node.getM_Index());
                        }
                    }

                }
            }
        }
        /**
         * If the heap is a max heap it is switched to a mix heap
         */
        public void switchMinHeap()
        {
            if (this.m_Type == 1)
            {
                toggleHeap();
            }

        }
        /**
         * If the heap is a min heap it is switched to a max heap
         */
        public void switchMaxHeap()
        {
            if (this.m_Type == 0)
            {
                toggleHeap();
            }
        }

        /**
         * Switch the heap to the opposite of what it is currently
         */
        public void toggleHeap()
        {
            FlexHeap<T> tmpFlex = new FlexHeap<T>(0, 0);

            if (this.m_Type == 0)
            {
                int size = this.m_Heap.getM_size();
                for (int i = 0; i < size; i++)
                {
                    tmpFlex.AddElement(this.Remove());
                }

                this.m_Type = 1;
                size = tmpFlex.m_Heap.getM_size();
                for (int i = 0; i < size; i++)
                {

                    this.AddElement(tmpFlex.Remove());
                }
            }
            else
            {
                int size = this.m_Heap.getM_size();
                for (int i = 0; i < size; i++)
                {
                    tmpFlex.AddElement(this.Remove());
                }

                this.m_Type = 0;
                size = tmpFlex.m_Heap.getM_size();

                for (int i = 0; i < size; i++)
                {
                    this.AddElement(tmpFlex.Remove());
                }
            }
        }

        /**
         *
         * @return Returns the root of the heap
         */
        public Node getRoot()
        {
            return this.m_Heap.Get(0);
        }


        /**
         * Takes a node and return the InOrder traversal from this node
         * @param root
         */
        private void inOrderPrint(Node root, List<T> _lists)
	    {
	      if (this.m_Heap.getLeftChild(root.getM_Index()) != null)
              inOrderPrint(this.m_Heap.getLeftChild(root.getM_Index()), _lists);
	       _lists.Add((T)root.getM_Value());
	  
	      if (this.m_Heap.getRightChild(root.getM_Index()) != null)
              inOrderPrint(this.m_Heap.getRightChild(root.getM_Index()), _lists);
	    }

        /**
         * Takes two nodes and swap their characters and keys
         * @param _Node
         * @param _Node2
         */
        public void SwapNodes(Node _Node, Node _Node2)
        {
            ConstraintKey tmpKey;
            T tmpValue;

            tmpKey = _Node.getM_Key();
            tmpValue = (T)_Node.getM_Value();

            _Node.setM_Key(_Node2.getM_Key());
            _Node.setM_Value(_Node2.getM_Value());

            _Node2.setM_Key(tmpKey);
            _Node2.setM_Value(tmpValue);
        }

        /**
         * 
         * @return True if the Heap is a MinHeap
         */
        public bool IsMinHeap()
        {
            return (this.m_Type == 0) ? true : false;
        }


        public List<T> OrderedElements
        {
            get
            {

                FlexHeap<T> clone = new FlexHeap<T>(this.m_Type, COMPARE_TYPE);
                

                List<T> tmpList = new List<T>();
                while (this.m_Heap.getM_size() > 0)
                {
                    Node node = this.Remove();
                    T item = (T)node.getM_Value();

                    tmpList.Add(item);

                    clone.AddElement(new Node(node));
                }

                this.m_Heap = clone.m_Heap;
                return tmpList;
            }

        }

        
    }

}
